package tree;

import queue.Queue;

public class BinaryTree<Key extends Comparable<Key>, Value> {
    //记录根节点
    private Node root;
    //记录元素的个数
    private int N;

    public int size(){
        return N;
    }
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    //向树中加值
    public Node put(Node n, Key key, Value value) {
        if (n == null) {
            N++;
            return new Node(key, value, null, null);
        }
        int com =key.compareTo(n.key);
        if (com > 0) {
            n.right = put(n.right, key, value);
        } else if (com < 0) {
            n.left = put(n.left, key, value);
        }else {
            n.value = value;
        }
        return n;
    }
    //从树中根据key找到对应的值
    public Value get(Key key){
       return get(root,key);
    }
    //根据对应的子树，找到对应的值
    public Value  get(Node x,Key key){
        if (x ==null){
            return null;
        }
        int com = key.compareTo(x.key);
        if (com>0){
           return get(x.right,key);
        }
        else if (com<0){
            return get(x.left,key);
        }
        else{
            return x.value;
        }
    }
    public void delete(Key key){
       root = delete(root,key);
    }
    public Node delete(Node x, Key key){
        if (x==null){
            return null;
        }

        int com = key.compareTo(x.key);
        //如果大于0，则取找树的右子树
        if (com>0){
            x.right = delete(x.right,key);
        }else if (com>0){
            x.left = delete(x.left,key);
        }else {
            //找到对应的值，开始很正的删除
            if (x.right == null){
                return x.left;
            }
            if (x.left == null){
                return x.right;
            }
            //如果该结点，既有左子树和右子树，则找到该结点右子树中的最小值，替换当前结点
            Node minNode = x.right;
            while (minNode.left!= null){
                minNode=minNode.left;
            }
            //删除最小结点
            Node n = x.right;
            while (n.left!=null){
                if (n.left.left ==null){
                    n.left=null;
                }else {
                    n=n.left;
                }
            }
            minNode.left=x.left;
            minNode.right=x.right;
            x=minNode;
            N--;
        }
        return x;
    }
    //查找二叉树中的最小的键
    public Key getMin(){
        return getMin(root).key;
    }
    public Node getMin(Node x){
        if (x.left!=null){
          return getMin(x.left);
        }else {
            return x;
        }
    }
    //查找二叉树中的最大的键
    public Key getMax(){
        return getMax(root).key;
    }
    public Node getMax(Node x){
        if (x.right!=null){
           return getMin(x.right);
        }else {
            return x;
        }
    }


    //前序遍历
    public Queue<Key> preErgodic(){
        Queue<Key> keys = new Queue<>();
        preErgodic(keys,root);
        return keys;
    }
    public void preErgodic(Queue<Key> keys , Node x){
    if (x == null){
        return;
    }
    keys.enqueue(x.key);
    if (x.left!=null){
        preErgodic(keys,x.left);
    }
    if (x.right != null){
        preErgodic(keys,x.right);
    }
    }

    //中序遍历
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        midErgodic(keys,root);
        return keys;
    }
    public void midErgodic(Queue<Key> keys, Node x){
        if (x==null){
            return;
        }
        if (x.left != null){
            midErgodic(keys,x.left);
        }
        keys.enqueue(x.key);
        if (x.right != null){
            midErgodic(keys,x.right);
        }
    }

    //后续遍历
    public Queue<Key> afterErgodic(){
        Queue<Key> keys =new Queue<>();
        afterErgodic(keys,root);
        return keys;
    }
    public void afterErgodic(Queue<Key> keys ,Node x ){
        if (x == null){
            return;
        }
        if (x.left != null){
            afterErgodic(keys,x.left);
        }
        if (x.right != null){
            afterErgodic(keys,x.right);
        }
        keys.enqueue(x.key);
    }

    //层序遍历
    public Queue<Key> layerErgodic(){
        Queue<Key> keys = new Queue<>();
        Queue<Node> node = new Queue<>();
        node.enqueue(root);
        while (!node.isEmpty()){
            Node n = node.dequeue();
            keys.enqueue(n.key);
            if (n.left != null){
                node.enqueue(n.left);
            }
            if (n.right != null){
                node.enqueue(n.right);
            }
        }
        return keys;
    }

    //计算树的最大深度
    public int maxDepth(){
        return maxDepth(root);
    }
    public int maxDepth(Node x){
        if (x ==null){
            return 0 ;
        }
        int max = 0;
        int maxL = 0;
        int maxR = 0;
        if (x.left != null){
           maxL = maxDepth(x.left);
        }
        if (x.right != null){
            maxR = maxDepth(x.right);
        }

        //4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
        max = maxL > maxR?maxL+1:maxR+1;
        return max;
    }



    private class Node {
        Key key;
        Value value;
        Node left;
        Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
